package com.acyouzi.leetcode.dp;

/**
 * 17/9/24 08:37
 *
 * @author sunxu
 */
public class PredictWinner {
  // Recursion
  public boolean PredictTheWinner(int[] nums) {
    return helper(nums,0,nums.length-1,1,0) >= 0;
  }
  private int helper(int[] nums, int start, int end, int flag,int sum) {
    if (start == end) return sum + flag * nums[start];
    int a =  helper(nums,start+1,end,-flag,sum+flag * nums[start]);
    int b =  helper(nums,start,end-1,-flag,sum+flag * nums[end]);
    // 如果 flag == 1 取的是最大值，否则取得是最小值
    return flag * Math.max(flag * a, flag * b);
  }

  // dp
  // 注意为什么第一个循环要倒着，因为 i 代表 start, j 代表 end 要求的是 i 到 j 之间的
  // 应该手写填充 dp 数组来推导
  // 不管哪一次抽，我都尽量保证我得到数字尽可能的大
  public boolean PredictTheWinnerDP(int[] nums) {
    int[][] dp = new int[nums.length][nums.length];
    for (int i = nums.length-2; i >= 0; i--) {
      dp[i][i] = nums[i];
      for (int j = i + 1; j < nums.length; j++) {
        dp[i][j] = Math.max(nums[j] - dp[i][j-1], nums[i] - dp[i+1][j]);
      }
    }
    return dp[0][nums.length-1] >= 0;
  }

}
